//
// Created by lwj12 on 24-8-17.
//

#ifndef LIST_LIST_H
#define LIST_LIST_H
#include <iostream>
using namespace std;
#include <algorithm>
#include <cassert>

namespace lwj
{
    template<class T>
    struct ListNode
    {
        ListNode<T>* _next;
        ListNode<T>* _prev;
        T _data;

        ListNode(const T& data = T())
            : _next(nullptr),
              _prev(nullptr),
              _data(data)
        {}
    };

    template<class T, class Ref, class Ptr>
    struct ListIterator
    {
        typedef struct ListNode<T> Node;
        typedef ListIterator<T, Ref, Ptr> Self;

        ListIterator(Node* node)
                : _node(node)
        {}

        Self& operator++() {_node = _node->_next; return *this;}
        Self& operator--() {_node = _node->_prev; return *this;}

        Self operator++(int)
        {
            Self tmp = *this;
            _node = _node->_next;
            return tmp;
        }

        Self operator--(int)
        {
            Self tmp = *this;
            _node = _node->_prev;
            return tmp;
        }

        Ref operator*() {return _node->_data;}
        Ptr operator->() {return &_node->_data;}

        bool operator==(const Self & t) {return _node == t._node;}
        bool operator!=(const Self & t) {return _node != t._node;}

        Node* _node;
    };

    template<class T, class Ref, class Ptr>
    struct Reverse_iterator
    {
        typedef struct ListNode<T> Node;
        typedef ListIterator<T, Ref, Ptr> It;
        typedef Reverse_iterator<T, Ref, Ptr> Self;

        Reverse_iterator(Node* node)
            : _it(node)
        {}

        Self& operator++() {--_it; return *this;}
        Self& operator--() {++_it; return *this;}
        Self operator++(int) {Self tmp = *this; --_it; return tmp;}
        Self operator--(int) {Self tmp = *this; ++_it; return tmp;}

        Ref operator*() {return *_it;}
        Ptr operator->() {return _it.operator->();}

        bool operator==(const Self& it) {return _it == it._it;}
        bool operator!=(const Self& it) {return _it != it._it;}

        It _it;
    };

    template<class T>
    class list
    {
    public:
        typedef struct ListNode<T> Node;
        typedef ListIterator<T, T&, T*> iterator;
        typedef ListIterator<T, const T&, const T*> const_iterator;
        typedef Reverse_iterator<T, const T&, const T*> const_Reverse_iterator;
        typedef Reverse_iterator<T, T&, T*> Reverse_iterator;

        iterator begin() {return iterator(_head->_next);}
        iterator end() {return iterator(_head);}

        const_iterator begin() const {return const_iterator(_head->_next);}
        const_iterator end() const {return const_iterator(_head);}

        Reverse_iterator rbegin() {return Reverse_iterator(_head->_prev);}
        Reverse_iterator rend() {return Reverse_iterator(_head);}

        const_Reverse_iterator rbegin() const {return const_Reverse_iterator(_head->_prev);}
        const_Reverse_iterator rend() const {return const_Reverse_iterator(_head);}

        void empty_init()
        {
            _head = new Node;
            _head->_prev = _head;
            _head->_next = _head;
        }

        list() {empty_init();}

        list(size_t n, const T& val = T())
        {
            empty_init();
            while (n--) push_back(val);
        }

        list(int n, const T& val = T())
        {
            empty_init();
            while (n--) push_back(val);
        }

        template<class InputIterator>
        list(InputIterator first, InputIterator last)
        {
            empty_init();
            for(auto it = first; it != last; it++) push_back(*it);
        }

        list(const list<T>& lt)
        {
            empty_init();
            for(const auto& e : lt) push_back(e);
        }

        list(initializer_list<T> il)
        {
            empty_init();
            for(const auto& e : il) push_back(e);
        }

        ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }


        list<T>& operator=(list<T> lt)
        {
            swap(_head, lt._head);
            return *this;
        }

        iterator insert(iterator pos, const T& data)
        {
            Node* newNode = new Node(data);
            newNode->_prev = pos._node->_prev;
            pos._node->_prev->_next = newNode;
            pos._node->_prev = newNode;
            newNode->_next = pos._node;
            return iterator(newNode);
        }

        iterator erase(iterator pos)
        {
            assert(!empty());
            Node* node = pos._node->_next;
            pos._node->_prev->_next = pos._node->_next;
            pos._node->_next->_prev = pos._node->_prev;
            delete pos._node;
            return iterator(node);
        }

        void push_back(const T& data) { insert(end(), data);}
        void push_front(const T& data) { insert(begin(), data);}
        void pop_back() {erase(--end());}
        void pop_front() {erase(begin());}

        bool empty() {return _head->_next == _head;}
        size_t size()
        {
            size_t sz = 0;
            for(auto it = begin(); it != end(); it++) sz++;
            return sz;
        }

        void clear()
        {
            while (!empty()) pop_back();
        }

    private:
        Node* _head;
    };
}

#endif//LIST_LIST_H
